package com.example.dynamicprogramming42;

/**
 * @description 回溯算法,最长公共子串长度
 * 最长公共子串长度的大小，表示两个字符串相似程度的大小
 * @auther lijiewei
 * @date 2022/5/16 16:26
 */
public class ComStrFlashBack {

    private char[] a = "mitcmu".toCharArray();
    private char[] b = "mtacnu".toCharArray();
    private int n = 6;
    private int m = 6;
    //最长公共子串长度
    private int maxCom = Integer.MIN_VALUE;

    public int getComStr() {
        comStr(0, 0, 0);
        return maxCom;
    }

    /**
     * 最长公共子串长度
     * 最长公共子串长度的大小，表示两个字符串相似程度的大小
     * @param i 数组a的指针
     * @param j 数组b的指针
     * @param comStr 还未处理a[i]和b[j]时，已经匹配的最长公共字符串
     * @return
     * @author lijiewei
     * @date   2022/5/16 20:18
     */
    private void comStr(int i, int j, int comStr) {
        if (i==n || j==m) {
            if (comStr > maxCom) {
                maxCom = comStr;
            }
            return;
        }
        //两个字符匹配
        if (a[i] == b[j]) {
            comStr(i+1, j+1, comStr+1);
        } else {
            //两个字符不匹配
            //删除a[i]或者b[j]前添加一个字符
            comStr(i+1, j, comStr);
            //删除b[j]或者a[i]前添加一个字符
            comStr(i, j+1, comStr);
        }
    }
}
